package main.回溯;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/7/19 17:14
 * @description
 */
public class T17电话号码的字母组合 {
    //定义数字到字母的映射
    String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    //result来存储结果
    List<String> result  =new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        LinkedList<String> list = new LinkedList<>();
        //条件判断
        if (digits == null || digits.length() == 0) {
            return list;
        }
        //先往list放入空串
        list.add("");
        //定义数字到字母的映射
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //遍历digits
        for (int i = 0; i < digits.length(); i++) {
            int digit = Character.getNumericValue(digits.charAt(i));
            //当队列中的字符串长度与当前处理的数字索引相同的时候，处理对立中的字符串
            while (list.peek().length() == i) {
                //从队列中取出一个字符串
                String t = list.remove();
                //遍历当前数字对应的所有字母
                for (char s : mapping[digit].toCharArray()) {
                    //将取出的字符串和当前的字母相结合，然后加入到队列里面
                    list.add(t+s);
                }
            }
        }
        return list;
    }

    /**
     * StringBuilder 来优化
     */
    public List<String> letterCombinations1(String digits) {
        LinkedList<StringBuilder> list = new LinkedList<>();
        //条件判断
        if (digits == null || digits.length() == 0) {
            return Collections.emptyList();
        }
        //先往list放StringBuilder，默认一开始存的是一个空的字符序列
        list.add(new StringBuilder());
        //定义数字到字母的映射
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //遍历digits
        for (int i = 0; i < digits.length(); i++) {
            int digit = Character.getNumericValue(digits.charAt(i));
            //当队列中的字符串长度与当前处理的数字索引相同的时候，处理队列中的字符串
            while (list.peek().length() == i) {
                //从队列中取出一个StringBuilder
                StringBuilder prefix = list.remove();
                //遍历当前数字对应的所有字母
                for (char s : mapping[digit].toCharArray()) {
                    //调用append方法，将s这个字符添加到当前字符序列的后面
                    list.add(new StringBuilder(prefix).append(s));
                }
            }
        }
        //StringBuilder 来转 String
        List<String> result  =new ArrayList<>();
        for (StringBuilder sb : list) {
            result.add(sb.toString());
        }
        return result;
    }


    /**
     * 回溯的做法
     * @param digits
     * @return
     */
    public List<String> letterCombinations2(String digits) {
        //条件判断
        if (digits == null || digits.length() == 0) {
            return Collections.emptyList();
        }
        //回溯
        backTrack(digits,0,new StringBuilder());
        return result;
    }

    public void backTrack(String digits,int index,StringBuilder sb){
        //如果当前处理的数字索引=字符串的长度，说明已经处理完了，把结果放入result里面
        if(index==digits.length()){
            result.add(sb.toString());
            return;
        }
        //获取当前数字字符
        char digit = digits.charAt(index);
        //获取当前数字字符对应的字母
        String letters = mapping[digit - '0'];
        //遍历当前数字字符对应的所有字母
        for (char letter : letters.toCharArray()) {
            //把字母加入到当前组合中
            sb.append(letter);
            //处理下一字符
            backTrack(digits,index+1,sb);
            //回溯
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
